#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long ll;
const int N = 1e6 + 10;

int qmi(ll a,ll k,ll p){
	int res = 1;
	while(k){
		if(k & 1) res = (ll)res * a % p;   //转换为二进制的末尾如果是1的话 
		k >>= 1;
		a = (ll)a * a % p;
	}
	
	return res;
}

void solve()
{
	ll a, k, p;
	cin >> a >> k >> p;
	cout << qmi(a, k, p) << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	cin >> t;
	while(t -- ) solve();
	return 0;
}

